/**
全排列2
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 */

/**
 * used[i] true 表示同一树枝使用过 需要跳过
 * nums[i-1]==nums[i]   used[i-1] false 表示同一树层使用过 需要跳过
 */
 var permuteUnique = function(nums) {
    const res = [];
    const path = [];
    const k = nums.length;
    const used = Array(k).fill(false);
    nums.sort((a,b)=> a-b);

    const backTrack = () => {
      if(path.length == k) {
        res.push(path.slice());
        return;
      }
      for(let i=0;i<k;i++) {
        if(used[i]) continue;
        if(i>0&&nums[i-1]==nums[i]&& used[i-1]==false) continue;
        used[i]=true;
        path.push(nums[i]);
        backTrack();
        path.pop();
        used[i]=false;
      }
    }
    backTrack();
    return res;
 };
 const nums = [1,1,2];
 console.log('全排列2',permuteUnique(nums));